/**
 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
 
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串
 */

const isPalindrome = (str) => {
  str = str.replace(/[^a-zA-Z\d]/g, '').toLowerCase()

  const length = str.length
  let i = 0

  while (i < length / 2) {
    if (str[i] !== str[str.length - 1 - i]) {
      return false
    }
    i++
  }

  return true
}

console.log(isPalindrome('A man, a plan, a canal: Panama'))


/**
 * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
 */
// 双指针解法
// 时间复杂度: 最好时为O(n), 最差时为O(n^2),n为s的长度
// 空间复杂度: o(1)
var validPalindrome = function (s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) {
      /**
       * 如果不相等,则分两种情况:删除左边的元素，或者右边的元素，
       * 再判断各自是否回文，满足一种即可。
       */
      return isPalinedrome(s, left + 1, right) || isPalinedrome(s, left, right - 1);
    }
    left++;
    right--;
  }
  return true;
};

// 判断字符串 s 的 [left, right] 是否回文
function isPalinedrome(s, left, right) {
  while (left < right) {
    if (s[left++] !== s[right--]) {
      return false;
    }
  }
  return true;
}

/**
 * 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
 * 请你返回让 s 成为回文串的 最少操作次数 。
 */
var minInsertions = function (s) {
  const dp = [];
  for (let i = 0; i < s.length; i++) {
    dp[i] = [];
    for (let j = 0; j < s.length; j++) {
      dp[i][j] = 0;
    }
  }
  for (let i = s.length - 1; i >= 0; i--) {
    for (let j = i + 1; j < s.length; j++) {
      dp[i][j] = Math.min(dp[i + 1][j] + 1, dp[i][j - 1] + 1);
      if (s[i] === s[j]) {
        dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
      }
    }
  }

  return dp[0][s.length - 1];
};